#include "Array2Tree.h"
#include <iostream>
#include <memory.h>
#include <stdlib.h>
#include <stdio.h>


using namespace std;

template<typename T>
Array2Tree<T>::Array2Tree(int arrayLength)
{
	if(arrayLength > 0)
	{
		this->parray = new char[arrayLength * sizeof(T) + EXT_LENGTH];

		if(!(this->parray))
		{
			cout << "system memory user up" << endl;
			exit(-1);
		}

		this->pTreeArray = (TreeNode<T>*)(parray + EXT_LENGTH);
		initIndex(arrayLength);
	}
	else
	{
		pTreeArray = NULL;
		parray = NULL;
	}

	filter = NULL;
}

template<typename T>
unsigned short Array2Tree<T>::getIndexValue(unsigned short index)
{
	if(index < LENGTH_INDEX || index > ROOT_INDEX)
	{
		cout << "wrong index for getIndexValue\n";
		exit(-1);
	}


	unsigned short *tmp = (unsigned short*)parray;
	return tmp[index];
}

template<typename T>
void Array2Tree<T>::initIndex(int totalLength)
{
	if(parray)
	{
		setIndexValue(ROOT_INDEX, 0);
		setIndexValue(LENGTH_INDEX, totalLength);
		setIndexValue(INUSE_INDEX, 0);
	}
}

template<typename T>
bool Array2Tree<T>::insert(const T& t)
{
	TreeNode<T> node(t);

	if(!parray)
		return false;

	int totalLength = getIndexValue(LENGTH_INDEX);
	int inUseLength = getIndexValue(INUSE_INDEX);

	if(inUseLength >= totalLength)
	{
		return false;
	}

	if(0 == inUseLength)
	{
		pTreeArray[0] = node;
		setIndexValue(INUSE_INDEX, 1);
		setIndexValue(ROOT_INDEX, 0);
		return true;
	}
	else
	{
		pTreeArray[getIndexValue(INUSE_INDEX)] = node;
		return innerInsert(getIndexValue(ROOT_INDEX), getIndexValue(INUSE_INDEX));
	}
}

template<typename T>
bool Array2Tree<T>::insert(const TreeNode<T> &node)
{
	if(!parray)
		return false;

	int totalLength = getIndexValue(LENGTH_INDEX);
	int inUseLength = getIndexValue(INUSE_INDEX);

	if(inUseLength >= totalLength)
	{
		return false;
	}

	//TODO INSERT FUNCTION

	//当前树为空
	if(inUseLength == 0)
	{
		pTreeArray[0] = node;
		setIndexValue(INUSE_INDEX, 1);
		setIndexValue(ROOT_INDEX, 0);
		return true;
	}
	else
	{
		pTreeArray[getIndexValue(INUSE_INDEX)] = node;
		return innerInsert(getIndexValue(ROOT_INDEX), getIndexValue(INUSE_INDEX));
	}

}

template<typename T>
const unsigned short Array2Tree<T>::getLength()
{
	return getIndexValue(LENGTH_INDEX);
}

template<typename T>
const unsigned short Array2Tree<T>::getinUse()
{
	return getIndexValue(INUSE_INDEX);
}

template<typename T>
const unsigned short Array2Tree<T>::getRootIndex()
{
	return getIndexValue(ROOT_INDEX);
}

template<typename T>
const TreeNode<T>* Array2Tree<T>::getArray()
{
	return this->pTreeArray;
}

template<typename T>
void Array2Tree<T>::setIndexValue(unsigned short index, unsigned short value)
{
	if(index < LENGTH_INDEX || index > ROOT_INDEX)
		return;

	unsigned short *tmp = (unsigned short*)this->parray;
	tmp[index] = value;
}

template<typename T>
bool Array2Tree<T>::innerInsert(unsigned short rootIndex, unsigned short  nodeIndex)
{
	if(pTreeArray[rootIndex] == pTreeArray[nodeIndex])
	{
		pTreeArray[rootIndex].setNode(pTreeArray[nodeIndex].getNode());
		return true;
	}

	if(pTreeArray[rootIndex] > pTreeArray[nodeIndex])
	{
		if(-1 == pTreeArray[rootIndex].getLeft())
		{
			pTreeArray[rootIndex].setLeft(nodeIndex);
			setIndexValue(INUSE_INDEX, getIndexValue(INUSE_INDEX) + 1);
			return true;
		}
		else
		{
			return innerInsert(pTreeArray[rootIndex].getLeft(), nodeIndex);
		}
	}
	else
	{
		if(-1 == pTreeArray[rootIndex].getRight())
		{
			pTreeArray[rootIndex].setRight(nodeIndex);
			setIndexValue(INUSE_INDEX, getIndexValue(INUSE_INDEX) + 1);
			return true;
		}
		else
		{
			return innerInsert(pTreeArray[rootIndex].getRight(), nodeIndex);
		}
	}
}

template<typename T>
void Array2Tree<T>::setFilterFun(filterFunction pfun)
{
	this->filter = pfun;
}

template<typename T>
void Array2Tree<T>::oneByone()
{
	if(getIndexValue(INUSE_INDEX) == 0)
		return;
	else
	{
		innerOneByone(getIndexValue(ROOT_INDEX));
	}
}

template<typename T>
void Array2Tree<T>::innerOneByone(int rootIndex)
{
	if(rootIndex == -1)
		return;

	innerOneByone((pTreeArray[rootIndex]).getLeft());
	//int x = (int)(pTreeArray[rootIndex].getNode());
	//cout << x << "--";

	if(filter)
	{
		filter(pTreeArray[rootIndex]);
	}

	innerOneByone((pTreeArray[rootIndex]).getRight());
}

template<typename T>
Array2Tree<T>::~Array2Tree()
{
	if(parray)
	{
		delete [] parray;
	}

	parray = NULL;
	pTreeArray = NULL;
}
